Booth's recode and the modified Booth's recode are well known methods of performing a multiplication using a reduced number of partial products. Conventionally, the multiplier and multiplicand are used to develop intermediate products that are added together to form the correct solution. The modified Booth's algorithm calls for the multiplier to be input to a circuit called a recode logic circuit in this application that shifts, inverts, or cancels out the multiplicand term to form partial products, depending on the value and position of a bit in the multiplier.
The method of performing the modified Booth's recode is illustrated, for example, in the text book called "Introduction to Arithmetic for Digital Systems Designers" by Waser and Flynn, published by Holt, Rinehart and Winston, New York. Conventionally, one adds a zero to the right of the least significant bit of the multiplier and, if necessary, pads the most significant bit with either zeros or ones depending on whether the number is unsigned or signed.
The known prior art relates to forming partial products within a single multiplier unit or sub-multiplier unit, the latter term being used to refer to the combination of registers and other hardware that performs the selection of partial products. The known prior art does not, however, teach one to divide a multiplier into two groups of bits and to operate on those bits in parallel simultaneously according to the modified Booth's recode to perform double precision multiplication or simply to speed up the operation.
The problem addressed by the subject invention is how to combine the results of two sub-multiplier units which carry out shifting and combining operations to form two sets of partial products that have been formed in accordance with the modified Booth's algorithm. If the two sets of partial products are added together in a straightforward manner, the result will be incorrect half the time.
In particular, the problem addressed by this invention is that of finding a circuit module that may be used in a set of identical chips to form an n-precision multiplication operation.